Chihik's Blog

An Ac a day, keeps the doctor away!

UVA1500 Alice and Bob

发布于 2020-09-28 | 分类于 博弈论 | 3分钟 | 477字数

这道题的状态挺难设计的。。。

令 ss 为石子的总数，那么操作次数最多为 s+(n−1)s+(n-1)

如果石子数量全不为一，那么先手必胜的条件为 s+(n−1)s+(n-1) 为奇数，因为他一定可以保证操作 s+(n−1)s+(n-1) 次。

阅读全文 »

P4056 [JSOI2009]火星藏宝图

发布于 2020-09-23 | 分类于 斜率优化 | 3分钟 | 472字数

首先有一个非常 naive 的 O(n2)\mathcal{O(n^2)} dp。

令 dpidp_i 表示到第 ii 座岛的最大收益，那么有：

dpi=max⁡1≤j≤n,j=i,xj≤xi,yj≤yi{dpj−(xi−xj)2−(yi−yj)2}+vidp_i=\max_{1\le j \le n, j \not= i ,x_j \le x_i ,y_j \le y_i }\{dp_j-(x_i-x_j)^2-(y_i-y_j)^2\}+v_i

阅读全文 »

P2120 [ZJOI2007]仓库建设

发布于 2020-09-23 | 分类于 斜率优化 | 3分钟 | 429字数

令 did_i 为工厂 ii 到工厂 nn （山底）的距离， dpidp_i 为在第 ii 个工厂建仓库的最小花费。

因为只能向下运，所以第 nn 个工厂必须建仓库存放它自己的产品，答案便为 dpndp_n

边界条件 dp0dp_0 为不建仓库的花费。

阅读全文 »

P3648 [APIO2014]序列分割

发布于 2020-09-23 | 分类于 斜率优化 | 3分钟 | 436字数

dp[t][i]=max⁡{dp[t−1][j]+sj(si−sj)}dp[t][i]=\max\{dp[t-1][j] + s_j(s_i-s_j)\}

dp[t][i]=max⁡{dp[t−1][j]+sjsi−sj2}dp[t][i]=\max\{dp[t-1][j] + s_js_i-s_j^2\}

阅读全文 »

P5504 [JSOI2011]柠檬

发布于 2020-09-23 | 分类于 斜率优化 | 4分钟 | 596字数

可以看出，选出区间的端点大小必须相同，不然可以将一端分在其他区间里，答案不会更劣。

令 dpidp_i 表示前 ii 个贝壳能得到的最大柠檬数， posipos_i 表示第 ii 个贝壳是第几个这种颜色的贝壳。

那么有转移：

阅读全文 »

P4072 [SDOI2016]征途

发布于 2020-09-22 | 分类于 斜率优化 | 3分钟 | 449字数

dp[i][j]=min(dp[i−1][k]+(Sumj−Sumk)2)   (0≤k<j)dp[i][j]=min(dp[i-1][k]+(Sum_j-Sum_k)^2) ~~~ (0 \le k < j)

dp[i][j]=min(dp[i−1][k]+Sumj2+Sumk2−2SumiSumk)   (0≤k<j)dp[i][j]=min(dp[i-1][k]+Sum_j^2+Sum_k^2-2Sum_iSum_k) ~~~ (0 \le k < j)

阅读全文 »

P2365 & P5785 任务安排

发布于 2020-09-22 | 分类于 斜率优化 、 二分 | 6分钟 | 911字数

两道题的转移式是一样的，只是优化不同。

令 dp(i)dp(i) 为完成前 ii 个任务的最小花费。

你会发现每次操作后总时间会增加 ss ，这样就不好处理当前时间。

阅读全文 »

CF906C Party

发布于 2020-09-17 | 分类于 状压dp | 2分钟 | 353字数

首先预处理出一个人能介绍的人的集合 relrel 。（包括他本身）

令 dp(S)dp(S) 表示让集合 SS 中的人相互认识最少需要几个人。

那么可以刷表转移：

阅读全文 »

UVA1407 Caves

发布于 2020-09-12 | 分类于 树形dp | 4分钟 | 730字数

一道标准的树形dp。

令 dp[u][i][0/1]dp[u][i][0/1] 表示以 uu 为根的子树 ， 探索 ii 个洞穴，是否回到 uu 。

显然有：

阅读全文 »
0%